package F.树;

import java.util.LinkedList;
import java.util.Queue;

public class _404_左叶子之和 {

    /**
     * 自解：层次遍历 弹出一个点 把他的左结点的值相加
     * ==hhh耗时死了
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        int left_val=0;
        if (root == null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            int size = queue.size();

            while (size>0){
                TreeNode node = queue.poll();

                if (node.left != null){
                    queue.add(node.left);
                    if (node.left.left == null && node.left.right == null){
                        left_val += node.left.val;
                    }

                }

                if (node.right != null){
                    queue.add(node.right);
                }

                size--;
            }
        }

        return left_val;


    }


    /**
     * 题解：深度优先遍历--如果是左结点 并且是叶子结点 就加
     * @param root
     * @return
     */

    public int sumOfLeftLeaves1(TreeNode root) {
        if (root == null){
            return 0;
        }

        return dfs(root);

    }

    public int dfs(TreeNode root){
        int result=0;//每一次一进来就清零了呀？？？---每一次递归进入结点的左叶子结点值 如果写成全局的话 就不能返回int了
        if (root.left !=null){
            result += isleaf(root.left)?root.left.val:dfs(root.left);
        }
        if (root.right != null && !isleaf(root.right)){
            result += dfs(root.right);
        }

        return result;
    }

    public boolean isleaf(TreeNode node){
        return node.left == null && node.right== null;
    }
}
